/*
 * Copyright 2006 Google Inc.
 * 
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not
 * use this file except in compliance with the License. You may obtain a copy of
 * the License at
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations under
 * the License.
 */
package java.util;

import java.util.Iterator;

public class HashMap extends AbstractMap implements Map, Cloneable {

  private static class ImplMapEntry implements Map.Entry {
    public boolean equals(Object a) {
      if (a instanceof Map.Entry) {
        Map.Entry s = (Map.Entry) a;
        boolean keyEquals = equalsWithNullCheck(fKey, s.getKey());
        if (equalsWithNullCheck(fKey, s.getKey())
          && equalsWithNullCheck(fValue, s.getValue())) {
          return true;
        }
      }
      return false;
    }

    public Object getKey() {
      return fKey;
    }

    public Object getValue() {
      return fValue;
    }

    public int hashCode() {
      int keyHash = 0;
      int valueHash = 0;
      if (fKey != null) {
        keyHash = fKey.hashCode();
      }
      if (fValue != null) {
        valueHash = fValue.hashCode();
      }
      return keyHash ^ valueHash;
    }

    public Object setValue(Object object) {
      Object old = fValue;
      fValue = object;
      return old;
    }

    private boolean equalsWithNullCheck(Object a, Object b) {
      if (a == b) {
        return true;
      } else if (a == null) {
        return false;
      } else {
        return a.equals(b);
      }
    }

    private boolean fInUse;

    private Object fKey;
    private Object fValue;
  }

  private class ImplMapEntryIterator implements Iterator {

    public ImplMapEntryIterator() {
      implAdvance();
    }

    public boolean hasNext() {
      if (fIndex < fEntries.length)
        return true;
      else
        return false;
    }

    // Don't double-check that the element exists; it's not worth the time.
    //
    public Object next() {
      fPrevIndex = fIndex;
      implAdvance();
      return fEntries[fPrevIndex];
    }

    public void remove() {
      if (fPrevIndex == -1)
        throw new IllegalStateException();
      else if (fEntries[fPrevIndex] != null)
        fEntries[fPrevIndex].fInUse = false;
    }


    private boolean implAdvance() {
      for (++fIndex; fIndex < fEntries.length; ++fIndex) {
        if (fEntries[fIndex] != null && fEntries[fIndex].fInUse)
          return true;
      }

      return false;
    }

    private int fIndex = -1;

    private int fPrevIndex = -1;
  }

  public HashMap() {
    this(37, 0.5f);
  }

  public HashMap(int initialCapacity) {
    this(initialCapacity, 0.5f);
  }

  public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0 || loadFactor <= 0)
      throw new IllegalArgumentException(
        "initial capacity was negative or load factor was non-positive");
    fEntries = new ImplMapEntry[initialCapacity];
    fLoadFactor = loadFactor;
  }

  public HashMap(Map m) {
    this(m.size());
    putAll(m);
  }

  public void clear() {
    fUsedSlots = 0;
    for (int i = 0, n = fEntries.length; i < n; ++i)
      fEntries[i] = null;
  }

  public Object clone() {
    return new HashMap(this);
  }

  public boolean containsKey(Object key) {
    int i = implFindSlot(key);
    if (i >= 0) {
      ImplMapEntry entry = fEntries[i];
      if (entry != null && entry.fInUse)
        return true;
    }
    return false;
  }

  public boolean containsValue(Object value) {
    return super.containsValue(value);
  }

  public Set entrySet() {
    return new AbstractSet() {
      public Iterator iterator() {
        return new ImplMapEntryIterator();
      }

      public int size() {
        return fUsedSlots;
      }
    };
  }

  public Object get(Object key) {
    int i = implFindSlot(key);
    if (i >= 0) {
      ImplMapEntry entry = fEntries[i];
      if (entry != null && entry.fInUse)
        return entry.fValue;
    }
    return null;
  }

  public int hashCode() {
    int accum = 0;
    Iterator elements = entrySet().iterator();
    while (elements.hasNext()) {
      accum += elements.next().hashCode();
    }
    return accum;
  }

  public Set keySet() {
    return super.keySet();
  }

  public Object put(Object key, Object value) {
    int newSize = size() + 1;
    if (newSize >= fLoadFactor * fEntries.length)
      implRehash();
    return implPutNoRehash(key, value, null);
  }

  public void putAll(Map m) {
    Set entrySet = m.entrySet();
    for (Iterator iter = entrySet.iterator(); iter.hasNext();) {
      Map.Entry entry = (Map.Entry) iter.next();
      put(entry.getKey(), entry.getValue());
    }
  }

  public Object remove(Object key) {
    int i = implFindSlot(key);
    if (i >= 0) {
      ImplMapEntry entry = fEntries[i];
      if (entry != null && entry.fInUse) {
        entry.fInUse = false;
        --fUsedSlots;
        return entry.getValue();
      }
    }
    return null;
  }

  public int size() {
    return fUsedSlots;
  }

  /**
   * Finds the index slot with the matching key or the first empty slot. This
   * method intentionally ignores whether or not an entry is marked "in use"
   * because the table implements "lazy deletion", meaning that every object
   * keeps its intrinsic location, whether or not it is considered still in the
   * table or not.
   * 
   * @return the index of the slot in which either the entry having the key was
   *         found or in which the entry would go; -1 if the hash table is
   *         totally full
   */
  private int implFindSlot(Object key) {
    int hashCode = (key != null ? key.hashCode() : 7919);
    hashCode = (hashCode < 0 ? -hashCode : hashCode);
    int capacity = fEntries.length;
    int startIndex = (hashCode % capacity);
    int slotIndex = startIndex;
    int stopIndex = capacity;
    for (int i = 0; i < 2; ++i) {
      for (; slotIndex < stopIndex; ++slotIndex) {
        Map.Entry entry = fEntries[slotIndex];
        if (entry == null)
          return slotIndex;

        Object testKey = entry.getKey();
        if (key == null ? testKey == null : key.equals(testKey))
          return slotIndex;
      }

      // Wrap around
      //
      slotIndex = 0;
      stopIndex = startIndex;
    }
    // The hash table is totally full and the matching item was not found.
    //
    return -1;
  }

  /**
   * Implements 'put' with the assumption that there will definitely be room for
   * the new item.
   */
  private Object implPutNoRehash(Object key, Object value,
      ImplMapEntry existingEntry) {
    int i = implFindSlot(key);
    // No need to check for (i == -1) because rehash would've made the array big
    // enough to find a slot
    if (fEntries[i] != null) {
      // Just updating the value that was already there.
      // Remember that the existing entry might have been deleted.
      //
      ImplMapEntry entry = fEntries[i];

      Object old = null;
      if (entry.fInUse)
        old = entry.fValue;
      else
        ++fUsedSlots;

      entry.fValue = value;
      entry.fInUse = true;
      return old;
    } else if (existingEntry == null) {
      // This a brand new (key, value) pair.
      // This branch is not taken during a rehash.
      //
      ++fUsedSlots;
      ImplMapEntry entry = new ImplMapEntry();
      entry.fKey = key;
      entry.fValue = value;
      entry.fInUse = true;
      fEntries[i] = entry;
      return null;
    } else {
      // This is a rehash, and we found the slot to move the old entry into.
      //
      fEntries[i] = existingEntry;
      return null;
    }
  }

  private void implRehash() {
    // Save the old entry array.
    //
    ImplMapEntry[] oldEntries = fEntries;

    // Allocate a new entry array that is twice as big as the last one.
    //
    int newCapacity = oldEntries.length * 2;
    if (newCapacity < 2)
      newCapacity = 2;
    fEntries = new ImplMapEntry[newCapacity];

    // Now put all the in-use entries from the old array into the new array.
    //
    for (int i = 0, n = oldEntries.length; i < n; ++i) {
      ImplMapEntry oldEntry = oldEntries[i];
      if (oldEntry != null && oldEntry.fInUse)
        implPutNoRehash(oldEntry.fKey, oldEntry.fValue, oldEntry);
    }
  }

  private ImplMapEntry[] fEntries;

  private float fLoadFactor;

  private int fUsedSlots;

}
